package demo.practice.tree.depth;

import demo.practice.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class P113 {

    List<List<Integer>> list = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null)
            return list;
        pathSum(root, targetSum, 0,new ArrayList<>());
        return list;
    }


    public void pathSum(TreeNode root, int targetSum, int sum,List<Integer> li) {

        if(root!=null){
            li.add(root.val);
            if(root.left==null&& root.right==null && sum+root.val==targetSum){
                list.add(new ArrayList<>(li));
            }
            if(root.left!=null){
                pathSum( root.left,  targetSum,  sum+root.val, new ArrayList<>(li));
            }
            if(root.right!=null){
                pathSum( root.right,  targetSum,  sum+root.val, new ArrayList<>(li));
            }
        }
    }

}
